package trees;

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;

/**
 * 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
 *
 * 示例 1:
 *
 * 输入: n = 12
 * 输出: 3
 * 解释: 12 = 4 + 4 + 4.
 * 示例 2:
 *
 * 输入: n = 13
 * 输出: 2
 * 解释: 13 = 4 + 9.
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/perfect-squares
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
public class NumSquares {

    //BFS
//    public int numSquares(int n) {
//        if(n == 0){
//            return 0;
//        }
//        if(n <= 1){
//            return 1;
//        }
//        Queue<Integer> queue = new ArrayDeque<>();
//        queue.add(n);
//        int count = 0;
//        while(!queue.isEmpty()){
//            int size = queue.size();
//            count ++;
//            for(int i = 0; i < size; i ++){
//                int v = queue.poll();
//                int k = 1;
//                while(true){
//                    int t = v - k * k;
//                    if(t == 0){
//                        return count + 1;
//                    }
//                    if(t < 0){
//                        break;
//                    }
//                    queue.add(t);
//                    k ++;
//                }
//            }
//        }
//
//        return count;
//    }

    //DP
    public int numSquares(int n){
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for(int i = 2; i <= n; i ++){
            dp[i] = i;
            for(int j = 1; i- j*j >= 0; j ++){
                dp[i] = Math.min(dp[i - j*j] + 1, dp[i]);
            }
        }
        return dp[n];
    }
}
